/*
 * 9.7
 * A circus is designing a tower routine consisting of people standing atop one anoth-
 * er’s shoulders. For practical and aesthetic reasons, each person must be both shorter
 * and lighter than the person below him or her. Given the heights and weights of each
 * person in the circus, write a method to compute the largest possible number of peo-
 * ple in such a tower.
 * EXAMPLE:
 * Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
 * Output: The longest tower is length 6 and includes from top to bottom: (56, 90)
 * (60,95) (65,100) (68,110) (70,150) (75,190)
 */
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

bool compare_pair(const pair<int, int> &a, const pair<int, int> &b)
{
    return (a.first < b.first) || (a.first == b.first && a.second < b.second);
}

bool less(const pair<int, int> &a, const pair<int, int> &b)
{
    return (a.first < b.first) && (a.second < b.second);
}

void search(int (*arr)[2], int n, vector<pair<int, int> > &out)
{
    vector<pair<int, int> > vp;
    for (int i = 0; i < n; i++) {
        vp.push_back(make_pair(arr[i][0], arr[i][1]));
    }
    std::sort(vp.begin(), vp.end(), compare_pair);

    vector<pair<int, int> > t;
    vector<pair<int, int> >::const_iterator it = vp.begin();
    vector<pair<int, int> >::const_iterator it2, it3;
    while (it != vp.end()) {
        t.clear();
        t.push_back(*it);

        it2 = it;
        while (it2 != vp.end()) {
            it3 = it2;
            while (it3 != vp.end()) {
                if (it3->first > it2->first && it3->second > it2->second) {
                    break;
                }
                it3++;
            }
            if (it3 != vp.end()) {
                t.push_back(*it3);
                it2 = it3;
            } else {
                if (out.size() == 0 || out.size() < t.size()) {
                    out.swap(t);
                }
                /* set it */
                it2 = it;
                while (it2 != vp.end() && it2->first == it2->first) {
                    it2++;
                }
                it = it2;
                it2 = vp.end(); /* break */
            }
        }
    }
}

int main()
{
    printf("=== test1 ===\n");
    int arr[][2] = {
        { 65, 100 },
        { 70, 150 },
        { 56, 90 },
        { 75, 190 },
        { 60, 95 },
        { 68, 110 }
    };
    int size = sizeof(arr)/sizeof(arr[0]);
    vector<pair<int, int> > out;
    search(arr, size, out);
    for (vector<pair<int, int> >::const_iterator it = out.begin(); it != out.end(); ++it) {
        printf("[%d,%d]\n", it->first, it->second);
    }
    printf("=== test2 ===\n");
    int arr2[][2] = {
        { 65, 120 },
        { 70, 150 },
        { 56, 90 },
        { 75, 190 },
        { 60, 88 },
        { 68, 110 }
    };
    size = sizeof(arr2)/sizeof(arr2[0]);
    out.clear();
    search(arr2, size, out);
    for (vector<pair<int, int> >::const_iterator it = out.begin(); it != out.end(); ++it) {
        printf("[%d,%d]\n", it->first, it->second);
    }
    return 0;
}
